Search results for "Lattice ga"
showing 10 items of 136 documents
One Alternation Can Be More Powerful Than Randomization in Small and Fast Two-Way Finite Automata
2013
We show a family of languages that can be recognized by a family of linear-size alternating one-way finite automata with one alternation but cannot be recognized by any family of polynomial-size bounded-error two-way probabilistic finite automata with the expected runtime bounded by a polynomial. In terms of finite automata complexity theory this means that neither 1Σ2 nor 1Π2 is contained in 2P2.
From deterministic cellular automata to coupled map lattices
2016
A general mathematical method is presented for the systematic construction of coupled map lattices (CMLs) out of deterministic cellular automata (CAs). The entire CA rule space is addressed by means of a universal map for CAs that we have recently derived and that is not dependent on any freely adjustable parameters. The CMLs thus constructed are termed real-valued deterministic cellular automata (RDCA) and encompass all deterministic CAs in rule space in the asymptotic limit $\kappa \to 0$ of a continuous parameter $\kappa$. Thus, RDCAs generalize CAs in such a way that they constitute CMLs when $\kappa$ is finite and nonvanishing. In the limit $\kappa \to \infty$ all RDCAs are shown to ex…
Semipredictable dynamical systems
2015
A new class of deterministic dynamical systems, termed semipredictable dynamical systems, is presented. The spatiotemporal evolution of these systems have both predictable and unpredictable traits, as found in natural complex systems. We prove a general result: The dynamics of any deterministic nonlinear cellular automaton (CA) with $p$ possible dynamical states can be decomposed at each instant of time in a superposition of $N$ layers involving $p_{0}$, $p_{1}$,... $p_{N-1}$ dynamical states each, where the $p_{k\in \mathbb{N}}$, $k \in [0, N-1]$ are divisors of $p$. If the divisors coincide with the prime factors of $p$ this decomposition is unique. Conversely, we also prove that $N$ CA w…
Automata and forbidden words
1998
Abstract Let L ( M ) be the (factorial) language avoiding a given anti-factorial language M . We design an automaton accepting L ( M ) and built from the language M . The construction is effective if M is finite. If M is the set of minimal forbidden words of a single word ν, the automaton turns out to be the factor automaton of ν (the minimal automaton accepting the set of factors of ν). We also give an algorithm that builds the trie of M from the factor automaton of a single word. It yields a nontrivial upper bound on the number of minimal forbidden words of a word.
On the Hierarchy Classes of Finite Ultrametric Automata
2015
This paper explores the language classes that arise with respect to the head count of a finite ultrametric automaton. First we prove that in the one-way setting there is a language that can be recognized by a one-head ultrametric finite automaton and cannot be recognized by any k-head non-deterministic finite automaton. Then we prove that in the two-way setting the class of languages recognized by ultrametric finite k-head automata is a proper subclass of the class of languages recognized by (k + 1)-head automata. Ultrametric finite automata are similar to probabilistic and quantum automata and have only just recently been introduced by Freivalds. We introduce ultrametric Turing machines an…
Varieties Generated by Certain Models of Reversible Finite Automata
2006
Reversible finite automata with halting states (RFA) were first considered by Ambainis and Freivalds to facilitate the research of Kondacs-Watrous quantum finite automata. In this paper we consider some of the algebraic properties of RFA, namely the varieties these automata generate. Consequently, we obtain a characterization of the boolean closure of the classes of languages recognized by these models.
Low-energy couplings of QCD from current correlators near the chiral limit
2004
We investigate a new numerical procedure to compute fermionic correlation functions at very small quark masses. Large statistical fluctuations, due to the presence of local ``bumps'' in the wave functions associated with the low-lying eigenmodes of the Dirac operator, are reduced by an exact low-mode averaging. To demonstrate the feasibility of the technique, we compute the two-point correlator of the left-handed vector current with Neuberger fermions in the quenched approximation, for lattices with a linear extent of L~1.5 fm, a lattice spacing a~0.09 fm, and quark masses down to the epsilon-regime. By matching the results with the corresponding (quenched) chiral perturbation theory expres…
Cellular automaton for chimera states
2016
A minimalistic model for chimera states is presented. The model is a cellular automaton (CA) which depends on only one adjustable parameter, the range of the nonlocal coupling, and is built from elementary cellular automata and the majority (voting) rule. This suggests the universality of chimera-like behavior from a new point of view: Already simple CA rules based on the majority rule exhibit this behavior. After a short transient, we find chimera states for arbitrary initial conditions, the system spontaneously splitting into stable domains separated by static boundaries, ones synchronously oscillating and the others incoherent. When the coupling range is local, nontrivial coherent struct…
Probing the chiral regime of Nf=2 QCD with mixed actions
2011
17 páginas, 15 figuras, 9 tablas.-- El Pdf es la versión pre-print del artículo: arXiv:1008.1870v2
Non Markovian Behavior of the Boltzmann-Grad Limit of Linear Stochastic Particle Systems
2007
We will review some results which illustrate how the distribution of obstacles and the shape of the characteristic curves influence the convergence of the probability density of linear stochastic particle systems to the one particle probability density associated with a Markovian process in the Boltzmann-Grad asymptotics.